1. Field of the Invention
The present invention relates to an image compressing technique, and more particularly it relates to an apparatus for performing an inverse discrete cosine transform (inverse DCT), which may be applied for decoding compressed image data.
2. Description of the Related Art
The inventors of the present invention know that the following two techniques (A) and (B) have been proposed in order to form an apparatus for performing an inverse discrete cosine transform (referred to as an inverse DCT).
(A) A technique of decomposing a two-dimensional inverse DCT into two one-dimensional inverse DCTs.
The inverse DCT is, as a transformation, a simple multiply-addition having a cosine function as its coefficient. To obtain the two-dimensional N-degree inverse DCT, where N represents a positive integer, the following equation (1) is used. ##EQU1## wherein F(u, v) denotes a pixel value of a compressed image, f (i, j) denotes a pixel value of a reconstructed image, and C(i, u, j, v), C(u) and C(v) are as follows. ##EQU2##
In general, the two-dimensional inverse DCT could be decomposed into two one-dimensional inverse DCTs.
At first, the one-dimensional inverse DCT is carried out in the row (horizontal) direction.
Second, the one-dimensional inverse ECT is carried out in the column (vertical) direction with respect to the result of the first inverse DCT. For the known technique, the direction of the inverse DCT to be done at the first time is fixed.
The two-dimensional inverse DCT of the equation (1) could be decomposed into a one-dimensional N-degree inverse DCT in the row (horizontal) direction as in equation (2), and a one-dimensional N-degree inverse DCT in the column (vertical) direction as in equation (3). ##EQU3## where F(u, v) denotes a pixel value of a compressed image, f.sup.c (i, v) denotes an output value of the row-directional inverse DCT, f (i, j) denotes a pixel value of a reconstructed image, and C(i, u), C(j, v), C(u) and C(v) are as follows. ##EQU4##
(B) A technique of performing a multiply-addition with considering zero inputs.
The two-dimensional inverse DCT receives, as an input, pixel values of the compressed image. Hence, the input contains a lot of zero elements. To cope with the input, it is known that the inverse DCT is performed considering such zero inputs. In one type of technique, any zero element is detected from the input elements, and only when a non-zero element is detected, the multiply-addition is carried out for implementing the inverse DCT.
In another technique, any zero element is detected, and only if a non-zero element is detected, is the value is stored in a RAM. The multiply-addition is carried out with respect to the value(s) stored in the RAM.
Now consider that the inverse DCT is carried out with respect to the input image consisting of N.times.N pixels. In this case, the required number of multiply-addition is derived as follows.
Assuming that the number of non-zero elements in N.times.N pixels is S, the number of rows having non-zero elements is P and the number of columns having non-zero elements is Q, then if the two-dimensional inverse DCT is carried out directly (without using the techniques (A) and (B) described above), the number of multiply-addition is N.sup.4. If two one-dimensional inverse DCTs are carried out (which holds true to the technique (A) only), then the number of multiply-addition is 2N.sup.3. If the two-dimensional inverse DCT is directly carried out considering non-zero elements (which holds true to the technique (B)), then the number is N.sup.2 S. If two one-dimensional inverse DCTs are carried out considering non-zero elements (which holds true to the techniques (A) and (B)), the number is NS+N.sup.2 P or NS+N.sup.2 Q.
Therefore, even though both of the above-mentioned known techniques (A) and (B) are used, the direction in which the inverse DCT is performed at first is fixed. Hence, it seems very probable that a direction requiring more multiply-additions may be selected, and this has been a serious drawback in the above-mentioned known techniques.